﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace Bouyei.Algo.Graph
{
    /// <summary>
    /// dijkstra最短路径搜索
    /// </summary>
    public class DijkstraAlgorithm
    {
        int rows = 0;
        DijkNode[] Graphic = null;
        int[,] graph = null;
        public const int NONE = int.MaxValue;

        public DijkstraAlgorithm(int sIndex, int[,] graph)
        {
            this.graph = graph;
            this.rows = graph.GetLength(0);
            Graphic = new DijkNode[rows];

            for (int i = 0; i < rows; ++i)
            {
                Graphic[i] = new DijkNode()
                {
                    Value = graph[sIndex, i]
                };
                Graphic[i].Path.Add(i);
            }

            //初始化该点已经访问
            //graphices[sIndex].Path.Add(sIndex);
            Graphic[sIndex].Visit = true;
            Graphic[sIndex].Value = 0;
        }

        public DijkNode[] Execute()
        {
            int temp = 0;

            while (true)
            {
                int min = NONE;
                int v = -1;

                //查找未访问过的最小的节点
                for (int j = 0; j < rows; ++j)
                {
                    if (Graphic[j].Visit || Graphic[j].Value == NONE) continue;

                    if (Graphic[j].Value < min)
                    {
                        v = j;
                        min = Graphic[j].Value;
                    }
                }

                if (v == -1) break;

                //标记该最短路径已经访问过
                Graphic[v].Visit = true;

                //根据该节点继续查找它的向外通路的边路径
                for (int k = 0; k < rows; ++k)
                {
                    if (Graphic[k].Visit || graph[v, k] == NONE) continue;//不通边直接过滤

                    temp = graph[v, k] + Graphic[v].Value;

                    if (temp < Graphic[k].Value)
                    {
                        Graphic[k].Value = temp;
                        Graphic[k].Path.Add(v);
                    }
                }
            }

            return Graphic.Where(x => x.Value != NONE).ToArray();
        }
    }

    public class DijkNode
    {
        public int Value { get; set; }//权重值
        public List<int> Path { get; set; }//保存当前最短路径的节点

        public bool Visit { get; set; }//是否已访问过

        public DijkNode()
        {
            Path = new List<int>(8);
        }
    }
}
